/**
 * 求两个链表的共同后缀的开始位置
 * 1. 求两个链表的长度
 * 2.对于较长的那个链表先走，走到后半部分和短链表长度相同的时候，两个链表的指针同时移动
 *  从第一个相同的元素开始标记为pre，如果相同就同时移动，且pre动，
 * 如果不同pre就要移动到当前指针位置的下一个位置重新记录
 */
#include"LinkedList.h"
/**
 * @param head 有头节点的链表
 */
int getLen(LinkedList *head){
    int len=0;
    while (head->next!=nullptr){
        len++;
        head=head->next;
    }
    return len;
}
/**
 * @param s1 有头节点
 * @return 公共后缀的头节点
 */
LinkedList * find_list(LinkedList* s1,LinkedList *s2){
    int m,n;//保存长度
    LinkedList *p,*q;//用来遍历的指针
    m=getLen(s1);
    n=getLen(s2);
    for(p=s1;m>n;m--){//m>n让p指向链表中的第m-n+1个节点
        p=p->next;
    }
    for(q=s2;m<n;n--){
        q=q->next;
    }
    while (p->next!=nullptr&&p->next!=q->next)
    {
        p=p->next;
        q=q->next;
    }
    return p->next;
}
//时间复杂度为O(len1+len2) 或者O(max(len1,len2))
